import java.util.Arrays;

public class QuickSort {
//快速排序是交换排序的其中之一，它由可以由递归实现。
    // 先选定一个基准值，把小于基准值的放在基准值的左边，大于基准值的放在基准值的右边
    //对左右两边进行递归
    //退出条件为： rightIdx-leftIdx<=1 时有序

    public static void quickSort(int[]arr,int leftIdx,int rightIdx){

        if(rightIdx-leftIdx<=1){
            return;
        }

        int pivotIdx=parttion(arr,leftIdx,rightIdx);

        quickSort(arr,leftIdx,pivotIdx-1);
        quickSort(arr,pivotIdx+1,rightIdx);

    }

    public static int parttion(int[]arr,int l,int r){

        int left=l;
        int right=r;
        int pivot=arr[r];

        while(left<right){

            while(left<right && arr[left]<=pivot){
                left++;
            }
            while(left<right && right>=pivot){
                right--;
            }

            swap(arr,left,right);
        }
        swap(arr,left,r);

        return left;

    }

    public static void swap(int[]arr,int i,int j){

        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void main(String[] args) {
        int[] arr={1,-5,7,1,-15,50};

        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}